import copy
import os
import random
import time

inputPath = './input/'
outputPath = './output/'
population = []
entites = []
Gnum = 0
Mnum = 0
length = 15
# 单个解最大迭代次数
trymax = 150

reference_point = [0,0]


def calculate_total_time(schedule):
    total_time = 0
    total_delay_time = 0
    delay_time = []
    for item in schedule:
        times = entites[item]['processing_time']
        curryTime = 0
        # 对于第一个工件直接相加
        if item == schedule[0]:
            for i in times:
                curryTime += i
                delay_time.append(curryTime)
        # 其他工件需要计算延迟时间
        else:
            for index, i in enumerate(times):
                # 第一个机器都会有延迟，直接加上延迟表中的第一项
                if index == 0:
                    # 更新当前时间
                    curryTime += delay_time[0] + i
                    # 更新延迟时间
                    delay_time[0] = curryTime
                else:
                    # 需要判断当前时间是否大于等于前一个工件的加工时间
                    if delay_time[index - 1] >= delay_time[index]:
                        curryTime += i
                        delay_time[index] = curryTime
                    # 否则需要加上上一个的等待时间
                    else:
                        # 时间差值
                        de = delay_time[index] - delay_time[index - 1]
                        curryTime = curryTime + de + i
                        delay_time[index] = curryTime
        # 计算延迟时间
        if delay_time[Mnum - 1] > entites[item]['delay']:
            total_delay_time += (delay_time[Mnum - 1] - entites[item]['delay'])
        # 计算总加工时间
        total_time += delay_time[Mnum - 1]
    # print(total_time)
    return total_time, total_delay_time


def readFile(filename):
    global entites, Gnum, Mnum
    with open(filename, 'r') as file:
        # 工件个数
        Gnum = int(file.readline())
        # 机器个数
        Mnum = int(file.readline())
        file.readline()
        while True:
            flag = 0
            entity = {}
            for i in range(0, 3):
                line = file.readline()
                if not line:
                    flag = 1
                    break
                if i == 0:
                    continue
                if i == 1:
                    entity['delay'] = int(line.strip())
                if i == 2:
                    entity['processing_time'] = list(map(int, line.strip().split()))
            entites.append(entity)
            if flag == 1:
                break


maxA = 0
maxB = 0


# 单个解上限50次
# flag =  1 先淘汰被占有  适应值最小
# flag =  1 淘汰适应值最小

def init():
    global population,reference_point
    population = []
    random_numbers = list(range(Gnum))
    #  确定参考点
    maxX = 0
    maxY = 0
    for i in range(0, length):
        random.shuffle(random_numbers)
        result_array = random_numbers[:Gnum]
        item = {}
        item['array'] = result_array
        item_time = calculate_total_time(result_array)
        # 计算总加工时间
        item['process'] = int(item_time[0])
        # 计算总延迟时间
        item['delay'] = (item_time[1])

        if (item['process'] > maxX):
            maxX = item['process']
        if (item['delay'] > maxY):
            maxY = item['delay']

        # 计算适应值
        item['fit'] = 0
        # flag
        item['flag'] = 0
        population.append(item)
    reference_point[0] = maxX + 1000
    reference_point[1] = maxY + 1000
    fitness()


def I(x, y):
    area_x = (reference_point[0] - x[0]) * (reference_point[1] - x[1])
    area_y = (reference_point[0] - y[0]) * (reference_point[1] - y[1])
    if (x[0] <= y[0] and x[1] <= y[1]) or (y[0] <= x[0] and y[1] <= x[1]):
        return area_x - area_y
    else:
        intersection_width = max(min(reference_point[0] - x[0], reference_point[0] - y[0]), 0)
        intersection_height = max(min(reference_point[1] - x[1], reference_point[1] - y[1]), 0)
        intersection_area = intersection_width * intersection_height
        return area_x - intersection_area


# 计算种群的适应值
def fitness():
    for i, item in enumerate(population):
        fit = 0
        for j, item2 in enumerate(population):
            if i != j:
                x = (population[i]['process'], population[i]['delay'])
                y = (population[j]['process'], population[j]['delay'])
                fit += I(x, y)
        population[i]['fit'] = fit
        # print('fit = ',fit)   [a,b,c,d,e,f,g]


# 计算解x的标志位
def calFlag(x):
    for item in population:
        # x在两个目标上严格占优某解
        if item['process'] > x['process'] and item['delay'] > x['delay']:
            # 更新标志位
            x['flag'] = 0
            return True
    # 当前解x不好，没有任何占优
    x['flag'] = 1
    return False


def getNew(x):
    # print(x)
    xTemp = copy.deepcopy(x)
    seek1 = random.randint(0, Gnum - 1)
    seek2 = random.randint(0, Gnum - 1)
    while seek1 == seek2:
        seek1 = random.randint(0, Gnum - 1)
        seek2 = random.randint(0, Gnum - 1)
    # 交换
    temp = xTemp['array'][seek1]
    xTemp['array'][seek1] = xTemp['array'][seek2]
    xTemp['array'][seek2] = temp

    item_time = calculate_total_time(xTemp['array'])

    # 计算总加工时间
    xTemp['process'] = int(item_time[0])
    # 计算总延迟时间
    xTemp['delay'] = (item_time[1])
    xTemp['fit'] = 0
    xTemp['flag'] = 0

    # 查询是否能放入？
    index = 0
    flag = calFlag(xTemp)
    while not flag:
        # print(index)
        index = index + 1
        if (index >= trymax):
            return False
        # 重新生成
        seek1 = random.randint(0, Gnum - 1)
        seek2 = random.randint(0, Gnum - 1)
        while seek1 == seek2:
            seek1 = random.randint(0, Gnum - 1)
            seek2 = random.randint(0, Gnum - 1)
        # 交换
        temp = xTemp['array'][seek1]
        xTemp['array'][seek1] = xTemp['array'][seek2]
        xTemp['array'][seek2] = temp

        item_time = calculate_total_time(xTemp['array'])

        # 计算总加工时间
        xTemp['process'] = int(item_time[0])
        # 计算总延迟时间
        xTemp['delay'] = (item_time[1])
        xTemp['fit'] = 0
        xTemp['flag'] = 0
        flag = calFlag(xTemp)
        # print(xTemp,flag,index)
    return xTemp

def getNewSff(x):
    # print(x)
    xTemp = copy.deepcopy(x)
    # print('__',xTemp['array'])
    random.shuffle(xTemp['array'])

    item_time = calculate_total_time(xTemp['array'])

    # 计算总加工时间
    xTemp['process'] = int(item_time[0])
    # 计算总延迟时间
    xTemp['delay'] = (item_time[1])
    xTemp['fit'] = 0
    xTemp['flag'] = 0

    # 查询是否能放入？
    index = 0
    flag = calFlag(xTemp)
    while not flag:
        # print(index)
        index = index + 1
        if (index >= trymax):
            return False
        # 重新生成
        seek1 = random.randint(0, Gnum - 1)
        seek2 = random.randint(0, Gnum - 1)
        while seek1 == seek2:
            seek1 = random.randint(0, Gnum - 1)
            seek2 = random.randint(0, Gnum - 1)
        # 交换
        temp = xTemp['array'][seek1]
        xTemp['array'][seek1] = xTemp['array'][seek2]
        xTemp['array'][seek2] = temp

        item_time = calculate_total_time(xTemp['array'])

        # 计算总加工时间
        xTemp['process'] = int(item_time[0])
        # 计算总延迟时间
        xTemp['delay'] = (item_time[1])
        xTemp['fit'] = 0
        xTemp['flag'] = 0
        flag = calFlag(xTemp)
        # print(xTemp,flag,index)
    return xTemp


# 更新标志位
def flagUpdate():
    n = len(population)
    for i in range(0, n):
        for j in range(0, n):
            if i != j:
                # 有解在两个目标上严格占优自己
                if population[i]['process'] > population[j]['process'] and \
                        population[i]['delay'] > population[j]['delay']:
                    # 更新标志位
                    population[i]['flag'] = 1
                    break


def main(filename):
    print('数据集：',filename)
    global population,reference_point
    begin = time.time()
    readFile(inputPath + filename)
    init()

    flagUpdate()
    times = 100000
    # for item in range(0, 3000):xz
    for item in range(0,times):
        print('\r','已完成：',str(round(item / times * 100,2)),'%，',round(time.time() - begin, 2), 's',end="")
        # for it in population:
        #     print(it['array'])
        # print()
        newX = getNew(population[item % length])

        # newX为False，说明该解的领域已经搜索50次以上了，采用下一个解
        if not newX:
            continue
        # 判断是否重复
        breakout = False
        for i in population:
          if newX['process'] == i['process'] and newX['delay'] == i['delay']:
            breakout = True
            break
        if breakout:
            continue
        # 找到flag为1的元素中fit最小的
        min_fit = float('inf')
        min_fit_index = None

        # 淘汰不好的
        for i, item in enumerate(population):
            if item['flag'] == 1 and item['fit'] < min_fit:
                min_fit = item['fit']
                min_fit_index = i

        # 如果没有flag为1的元素，找到flag为0中fit最小的
        if min_fit_index is None:
            for i, item in enumerate(population):
                if item['flag'] == 0 and item['fit'] < min_fit:
                    min_fit = item['fit']
                    min_fit_index = i

        # 删除最小的元素
        if min_fit_index is not None:
            del population[min_fit_index]
        # 添加新解
        population.append(newX)
        fitness()
        flagUpdate()
    end = time.time()
    population = sorted(population, key=lambda x: x['fit'], reverse=True)
    for item in population:
        print(item['process'], item['delay'], item['fit'], item['flag'])
    print('运行时间：', round(end - begin, 2), 's')
    with open(outputPath + filename, 'w') as file:
        for i in population:
            line = 'array = {},process = {}, delay = {}, fit = {}, flag = {}'.format(i['array'],i['process'], i['delay'], i['fit'], i['flag'])
            file.write(line + '\n')



if __name__ == "__main__":
    for root, dirs, files in os.walk(inputPath):
        for file in files:
            # 初始化全局变量
            Mnum = 0
            Gnum = 0
            population = []
            reference_point = [0,0]
            entites = []
            file_name = file
            main(file_name)
